package structure.algorithm;

import java.math.BigDecimal;

/**
 * 使用二分法查找有序数组（顺序为从小到大）中的指定元素
 * @author fidel
 */
public class BinarySearch {
    private static BigDecimal DIVISOR = BigDecimal.valueOf(2);
    private static BigDecimal ADDEND = BigDecimal.valueOf(0.5);
    
    static boolean search(int[] arrays, final int value) {
        if (arrays == null || arrays.length == 0) {
            return false;
        }
        // 检测数组中的元素的排列顺序是否是从小到大
        for (int i = 1; i < arrays.length; i++) {
            if (arrays[i - 1] > arrays[i]) {
                System.out.println("参数数组的排列顺序不符合规范");
                return false;
            }
        }
        int head = 0, tail = arrays.length - 1, length = tail + 1 - head;
        BigDecimal sum, previous, next, middle, dividend;
        // 当头部指针与尾部指针两端之间的元素数目不小于1时
        while (length > 0) {
            // 如果数组长度为1
            if (length == 1) {
                return arrays[0] == value ? true : false;
            } else if (length == 2) {
                return arrays[head] == value || arrays[tail] == value ? true : false;
            } else {
                // sum的值等于头部索引与尾部索引的和
                sum = new BigDecimal(head + tail);
                // sum除以2的商减0.5
                previous = sum.divide(DIVISOR).subtract(ADDEND);
                // sum除以2的商加0.5
                next = sum.divide(DIVISOR).add(ADDEND);
                dividend = new BigDecimal(arrays[previous.intValue()] + arrays[next.intValue()]);
                // 如果数组长度为偶数
                if (length % 2 == 0) {
                    // middle的值等于被除数除以2
                    middle = dividend.divide(DIVISOR);
                } else {
                    // 数组长度为奇数，取中间值作为中位数
                    middle = new BigDecimal(arrays[sum.divide(DIVISOR).intValue()]);
                }
                sum = sum.divide(DIVISOR);
                // 如果待检测值小于中位数
                if (middle.compareTo(BigDecimal.valueOf(value)) == 1) {
                    // 如果数组长度为偶数
                    if (length % 2 == 0) {
                        // 数组尾部索引的值等于sum减0.5
                        tail = sum.subtract(ADDEND).intValue();
                    } else {
                        // 数组尾部索引的值等于sum减1
                        tail = sum.subtract(BigDecimal.ONE).intValue();
                    }
                    // 更新length的值
                    length = tail + 1 - head;
                    // 否则，如果待检测值大于中位数
                } else if (middle.compareTo(BigDecimal.valueOf(value)) == -1) {
                    if (length % 2 == 0) {
                        // 数组头部索引的值等于sum加0.5
                        head = sum.add(ADDEND).intValue();
                    } else {
                        // 数组头部索引的值等于sum加1
                        head = sum.add(BigDecimal.ONE).intValue();
                    }
                    length = tail + 1 - head;
                } else {
                    // 待检测值等于中位数
                    // 如果当前数组的长度为奇数，那么该数组中包含此待检测值
                    return length % 2 == 1 ? true : false;
                }
            }
        }
        return false;
    }
}
